package it.storm.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 73. 矩阵置零
 * https://leetcode-cn.com/problems/set-matrix-zeroes/
 */
public class Solutions_73 {
    public static void main(String[] args) {
        int[][] matrix1 = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
        // output: {{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}

        int[][] matrix2 = {{0, 1, 2, 0}, {3, 4, 5, 2}, {1, 3, 1, 5}};
        // output: {{0, 0, 0, 0}, {0, 4, 5, 0}, {0, 3, 1, 0}}

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(matrix1);
        inputs.add(matrix2);
        for (int[][] input : inputs) {
            setZeroes(input);
            System.out.println(Arrays.deepToString(input));
        }
    }

    /**
     * 解法二：空间复杂度（常量解法）
     * 1.通过 rowFlag, colFlag 标记出第一行，第一列是否需要置 0
     *      （即行或列中是否有 0）
     * 2.遍历 [1, 1] 及以后的元素，若 [i, j] 为 0，
     *      则对应的第 1 行和第 1 列的元素标记为 0
     * 3.不要忘了第一行和第一列本身，若 rowFlag = true，说明第一行需要全部置 0
     *      若 colFlag = true，说明第一列需要全部置 0
     */
    public static void setZeroes(int[][] matrix) {
        boolean rowFlag = false, colFlag = false;
        int row = matrix.length, col = matrix[0].length;
        for (int i = 0; i < col; i++) {
            if (matrix[0][i] == 0) {
                // 第 1 行需要全部置 0
                rowFlag = true;
                break;
            }
        }
        for (int i = 0; i < row; i++) {
            if (matrix[i][0] == 0) {
                // 第 1 列需要全部置 0
                colFlag = true;
                break;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (matrix[i][j] == 0) {
                    // 对应的第 1 行和第 1 列的元素修改为 0
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for (int i = 1; i < col; i++) {
            if (matrix[0][i] == 0) {
                // 第 i 列需要全部置 0
                for (int j = 1; j < row; j++) {
                    matrix[j][i] = 0;
                }
            }
        }
        for (int i = 1; i < row; i++) {
            if (matrix[i][0] == 0) {
                // 第 i 行需要全部置 0
                for (int j = 1; j < col; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (rowFlag) {
            // 第 1 行中有元素 0，那么整行为 0
            for (int i = 0; i < col; i++) {
                matrix[0][i] = 0;
            }
        }
        if (colFlag) {
            // 第 1 列中有元素 0，那么整列为 0
            for (int i = 0; i < row; i++) {
                matrix[i][0] = 0;
            }
        }
    }

    /**
     * 解法一：空间复杂度（m + n 解法）
     * rowFlag[0] = true，第 1 行需要全部置 0
     * colFlag[1] = true，第 2 行需要全部置 0
     * 第 1 次遍历，若当前元素为 0，则修改 rowFlag 和 colFlag
     * 第 2 次遍历，若当前元素不为 0，且本行或者本列需要置 0，则设置值为 0
     */
    public static void setZeroes2(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        boolean[] rowFlag = new boolean[row];
        boolean[] colFlag = new boolean[col];

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    rowFlag[i] = true;
                    colFlag[j] = true;
                }
            }
        }
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] != 0 && (rowFlag[i] || colFlag[j])) {
                    matrix[i][j] = 0;
                }
            }
        }
    }
}
